#include "Moves.hpp"
#include <algorithm>
#include <set>


Moves::InterMoveFunc    Moves::InterMoves[TWO_OPT_S + 1] = 
{
    Moves::InterOrOpt,
    Moves::InterTwoOptS
};

Moves::IntraMoveFunc    Moves::IntraMoves[SWAP + 1] = 
{
    Moves::IntraSwap
};

Moves* Moves::Instance = 0;

unsigned Moves::Move::NextId = 0;

void     Moves::buildInstance(VRPTW& inVRPTW)
{
    if (Moves::Instance == 0)
        Moves::Instance = new Moves(inVRPTW);
}

void     Moves::delInstance()
{
    if (Moves::Instance != 0)
        delete Moves::Instance;

    Moves::Instance = 0;
}

Moves&   Moves::getInstance()
{
    assert(Moves::Instance != 0);
    return (*Moves::Instance);
}



// inV2 absorbe un client de inV1
void         Moves::InterOrOpt(Vehicle& inV1, Vehicle& inV2, unsigned inSubIndex)
{
    std::deque<Trio>    oropts;
    char				buffer[0x1000];
    VRPTW&   			vrptw = *inV1.veVRPTW;
    unsigned char		pred;
    unsigned char		succ;
    unsigned char		next;
    unsigned			k = 0;
    
    // calcul de toutes les insertions possibles V1 -> V2
    for (Vehicle::Iterator it1 = inV1.bdepot() ; it1 != inV1.edepot() ; ++it1)
    {
        if (it1 == inV1.bdepot())
            continue;
        
        for (Vehicle::Iterator it2 = inV2.bdepot() ; it2 != inV2.edepot() ; ++it2)
        {
#ifdef USING_CHECK_INSERT3
            if (vrptw.checkInsert3(     it2.info(),
                                        inV2.veInfos[inV2.veSuccs[it2.info().siClient]],
                                        it1.info().siClient,
                                        inV2.edepot().info().siCCapacityAtArrival) != VRPTW::REALIZABLE_NONE)
#endif
#ifdef USING_CHECK_INSERT4
            if (vrptw.checkInsert4(     inV2,
										it2.info().siClient,
                                        inV2.veInfos[inV2.veSuccs[it2.info().siClient]].siClient,
                                        it1.info().siClient,
                                        inV2.edepot().info().siCCapacityAtArrival) != VRPTW::REALIZABLE_NONE)
#endif
                oropts.push_back(Trio(it2.info().siClient, inV2.veInfos[inV2.veSuccs[it2.info().siClient]].siClient, it1.info().siClient));
        }
        
		//if (oropts.size() == 1)
		//	break;
    }
    
    // si aucune insertion possible on se barre
    if (oropts.size() == 0)
        return;
        
    inSubIndex %= oropts.size();
    
	for (k = 0 ;; k++)
	{
		next = inV1.veSuccs[oropts[inSubIndex].third];
		pred = oropts[inSubIndex].third;
		succ = oropts[inSubIndex].second;
		inV1.erase(oropts[inSubIndex].third);
		inV2.insert(oropts[inSubIndex].third, oropts[inSubIndex].first, oropts[inSubIndex].second);
		
		if (		(next != (vrptw.size() + 1)) 
				&& 
#ifdef USING_CHECK_INSERT3
					vrptw.checkInsert3	(	inV2.veInfos[pred],
											inV2.veInfos[succ],
											next,
											inV2.edepot().info().siCCapacityAtArrival)
								!= VRPTW::REALIZABLE_NONE)
#endif
#ifdef USING_CHECK_INSERT4
					vrptw.checkInsert4	(	inV2,
											inV2.veInfos[pred].siClient,
											inV2.veInfos[succ].siClient,
											next,
											inV2.edepot().info().siCCapacityAtArrival)
								!= VRPTW::REALIZABLE_NONE)
#endif
		{	
			oropts[inSubIndex].first = pred;
			oropts[inSubIndex].second = succ;
			oropts[inSubIndex].third = next;
		}
		else
		{
			break;
		}
	}
	
	//std::cout << "oropt " << (k + 1) << std::endl;
}

// algorithme supreme en deux etapes :
//		- 1ere etape : exchange des last jusqu'au blocage sur un vehicule
//		- 2eme etape : si blocage sur seulement 1 vehicule alors lock du current sur vehicule bloque
//						et insertion after
void         Moves::InterTwoOptS(Vehicle& inV1, Vehicle& inV2, unsigned inSubIndex)
{
	unsigned char	v1_pred;
	unsigned char	v1_cur;
	unsigned char	v1_succ;
	unsigned char	v2_pred;
	unsigned char	v2_cur;
	unsigned char	v2_succ;
	
	VRPTW&   		vrptw = *inV1.veVRPTW;
	
	bool			v1_impossible = false;
	bool			v2_impossible = false;
	
	// démarrer avec les derniers clients
	v1_cur = inV1.vePreds[inV1.edepot().info().siClient];
	v2_cur = inV2.vePreds[inV2.edepot().info().siClient];
	
	for (;;)
	{
		// preds/succs
		v1_pred = inV1.vePreds[v1_cur];
		v1_succ = inV1.veSuccs[v1_cur];
		v2_pred = inV2.vePreds[v2_cur];
		v2_succ = inV2.veSuccs[v2_cur];
		
		if (v1_pred == 0xFE || v2_pred == 0xFE)
		{
			break;
		}
		
		
		// supprimer des tournées
		inV1.erase(v1_cur);
		inV2.erase(v2_cur);
		
		// verifier insertion dans V1
		v2_impossible = (
#ifdef USING_CHECK_INSERT3
							vrptw.checkInsert3(	inV1.veInfos[v1_pred],
												inV1.veInfos[v1_succ],
												v2_cur,
												inV1.edepot().info().siCCapacityAtArrival) 
#endif
#ifdef USING_CHECK_INSERT4
							vrptw.checkInsert4(	inV1,
												inV1.veInfos[v1_pred].siClient,
												inV1.veInfos[v1_succ].siClient,
												v2_cur,
												inV1.edepot().info().siCCapacityAtArrival) 
#endif					
							== VRPTW::REALIZABLE_NONE);
														
		// verifier insertion dans V1
		v1_impossible = (
#ifdef USING_CHECK_INSERT3
							vrptw.checkInsert3(	inV2.veInfos[v2_pred],
												inV2.veInfos[v2_succ],
												v1_cur,
												inV2.edepot().info().siCCapacityAtArrival) 
#endif
#ifdef USING_CHECK_INSERT4
							vrptw.checkInsert4(	inV2,
												inV2.veInfos[v2_pred].siClient,
												inV2.veInfos[v2_succ].siClient,
												v1_cur,
												inV2.edepot().info().siCCapacityAtArrival) 
#endif
							== VRPTW::REALIZABLE_NONE);
		
		if (v1_impossible)
		{
			if (v2_impossible)
			{
				// annuler erase et degager, c'est fini on ne peut plus rien faire
				inV1.insert(v1_cur, v1_pred, v1_succ);
				inV2.insert(v2_cur, v2_pred, v2_succ);
				return;
			}
			else
			{
				// annuler modifs, v1_cur devient reference pour insertion after dans V1
				inV1.insert(v1_cur, v1_pred, v1_succ);
				inV2.insert(v2_cur, v2_pred, v2_succ);
				
				if (v2_cur == inV2.bdepot().info().siClient)
						return;
					
				
				v1_pred = v1_cur;				// v1_pred ne changera jamais
				v1_succ = inV1.veSuccs[v1_cur];
									
				
				while (	
#ifdef USING_CHECK_INSERT3
						vrptw.checkInsert3(		inV1.veInfos[v1_pred],
												inV1.veInfos[v1_succ],
												v2_cur,
												inV1.edepot().info().siCCapacityAtArrival)
#endif
#ifdef USING_CHECK_INSERT4
						vrptw.checkInsert4(		inV1,
												inV1.veInfos[v1_pred].siClient,
												inV1.veInfos[v1_succ].siClient,
												v2_cur,
												inV1.edepot().info().siCCapacityAtArrival)
#endif
												!= VRPTW::REALIZABLE_NONE)
				{
					if (v2_cur == inV2.bdepot().info().siClient)
						break;
					
					v2_pred = inV2.vePreds[v2_cur];
					inV2.erase(v2_cur);
					inV1.insert(v2_cur, v1_pred, v1_succ);
					v1_succ = v2_cur;	// succ pour insertion devient le nouveau vertex
					v2_cur = v2_pred;	// tentative d'insertion de l'ancien predecesseur de v2_cur
					
					if (v2_pred == 0xFE)
						break;
						
					if (v2_cur == inV2.bdepot().info().siClient)
						break;
				}
				break;
			}
		}
		else
		{
			if (v2_impossible)
			{	
				// annuler modifs, v2_cur devient reference pour insertion after dans V2
				inV1.insert(v1_cur, v1_pred, v1_succ);
				inV2.insert(v2_cur, v2_pred, v2_succ);

				if (v1_cur == inV1.bdepot().info().siClient)
						return;

				v2_pred = v2_cur;				// v2_pred ne changera jamais
				v2_succ = inV2.veSuccs[v2_cur];
				
				while (
#ifdef USING_CHECK_INSERT3
						vrptw.checkInsert3(		inV2.veInfos[v2_pred],
												inV2.veInfos[v2_succ],
												v1_cur,
												inV2.edepot().info().siCCapacityAtArrival) 
#endif
#ifdef USING_CHECK_INSERT4
						vrptw.checkInsert4(		inV2,
												inV2.veInfos[v2_pred].siClient,
												inV2.veInfos[v2_succ].siClient,
												v1_cur,
												inV2.edepot().info().siCCapacityAtArrival) 
#endif
						!= VRPTW::REALIZABLE_NONE)
				{
					if (v1_cur == inV1.bdepot().info().siClient)
						break;
					
					v1_pred = inV1.vePreds[v1_cur];
					inV1.erase(v1_cur);
					inV2.insert(v1_cur, v2_pred, v2_succ);
					v2_succ = v1_cur;	// succ pour insertion devient le nouveau vertex
					v1_cur = v1_pred;	// tentative d'insertion de l'ancien predecesseur de v1_cur
					
					if (v1_pred == 0xFE)
						break;
						
				if (v1_cur == inV1.bdepot().info().siClient)
						break;;
				}
				
				break;
			}
			else
			{
				// insert valides, on les execute
				inV1.insert(v2_cur, v1_pred, v1_succ);
				inV2.insert(v1_cur, v2_pred, v2_succ);
				v2_cur = v2_pred;
				v1_cur = v1_pred;
			}
		}
	}
}


void        Moves::IntraSwap(Vehicle& inV, unsigned inSubIndex)
{
	
}

Moves::Moves(VRPTW& inVRPTW)
    : moVRPTW(inVRPTW)
{
    moMoves = new Moves::Move***[Moves::INTRA + 1];
    for (unsigned gt = Moves::INTER ; gt != (Moves::INTRA + 1) ; gt++)
    {
        if (gt == Moves::INTER)
        {
            moMoves[gt] = new Moves::Move**[Moves::TWO_OPT_S + 1];
            for (unsigned intert = Moves::OR_OPT ; intert != (Moves::TWO_OPT_S + 1) ; intert++)
            {
                if (intert == Moves::OR_OPT)
                {
                   moMoves[gt][intert] = new Move*[(moVRPTW.size() * moVRPTW.size())];
                   for (unsigned i = 0 ; i < moVRPTW.size() ; i++)
                   {
                       for (unsigned j = 0 ; j < moVRPTW.size() ; j++)
                       {
                            if (i == j)
                                continue;
                           
                            moMoves[gt][intert][i * moVRPTW.size() + j] = new InterMove(Moves::OR_OPT, i, j);
                       }
                   } 
                }
                else if (intert == Moves::TWO_OPT_S)
                {
                    moMoves[gt][intert] = new Move*[(moVRPTW.size() * moVRPTW.size())];
                   for (unsigned i = 0 ; i < moVRPTW.size() ; i++)
                   {
                       for (unsigned j = 0 ; j < moVRPTW.size() ; j++)
                       {
                            if (i == j)
                                continue;
                           
                            moMoves[gt][intert][i * moVRPTW.size() + j] = new InterMove(Moves::TWO_OPT_S, i, j);
                       }
                   } 
                }
                
            }
        }
        else
        {
            moMoves[gt] = new Moves::Move**[Moves::SWAP + 1];
            
            for (unsigned intrat = Moves::SWAP ; intrat != (Moves::SWAP + 1) ; intrat++)
            {
                if (intrat == Moves::SWAP)
                {
                    moMoves[gt][intrat] = new Move*[(moVRPTW.size())];
                    for (unsigned i = 0 ; i < moVRPTW.size() ; i++)
                        moMoves[gt][intrat][i] = new IntraMove(Moves::SWAP, i);
                }
                else
                {}
            }
        }
    }
}

Moves::~Moves()
{
    for (unsigned gt = Moves::INTER ; gt != (Moves::INTRA + 1) ; gt++)
    {
        if (gt == Moves::INTER)
        {
            for (unsigned intert = Moves::OR_OPT ; intert != (Moves::TWO_OPT_S + 1) ; intert++)
            {
                if (intert == Moves::OR_OPT)
                {
                   for (unsigned i = 0 ; i < moVRPTW.size() ; i++)
                   {
                       for (unsigned j = 0 ; j < moVRPTW.size() ; j++)
                       {
                            if (i == j)
                                continue;
                           
                            delete moMoves[gt][intert][i * moVRPTW.size() + j];
                       }
                   }
                   delete [] moMoves[gt][intert];
                }
                else if (intert == Moves::TWO_OPT_S)
                {
                   for (unsigned i = 0 ; i < moVRPTW.size() ; i++)
                   {
                       for (unsigned j = 0 ; j < moVRPTW.size() ; j++)
                       {
                            if (i == j)
                                continue;
                           
                            delete moMoves[gt][intert][i * moVRPTW.size() + j];
                       }
                   }
                   delete [] moMoves[gt][intert];
                }
            }
            delete [] moMoves[gt];
        }
        else
        {
            for (unsigned intrat = Moves::SWAP ; intrat != (Moves::SWAP + 1) ; intrat++)
            {
                if (intrat == Moves::SWAP)
                {
                    for (unsigned i = 0 ; i < moVRPTW.size() ; i++)
                        delete moMoves[gt][intrat][i];
                    
                    delete [] moMoves[gt][intrat];
                }
                else
                {}
            }
            delete [] moMoves[gt];
        }
    }
    delete [] moMoves;
}

unsigned	Moves::fillNeighborhoodsBuffer(const Sol& inSol, Moves::Move* inBuffer[], unsigned inMax) const
{
	unsigned					i;
	unsigned					n;
	// thx K. Bogtob
	std::set<unsigned char>::iterator		it1;
	std::set<unsigned char>::iterator		it2;
	std::set<unsigned char>		vehicles1;
	std::set<unsigned char>		vehicles2;
	
	for (i = 0 ; i < moVRPTW.size() ; i++)
	{
		if (inSol.getTourneeByClient()[i] == 0xFF)
			continue;
		
		if (vehicles1.find(inSol.getTourneeByClient()[i]) == vehicles1.end())
			vehicles1.insert(inSol.getTourneeByClient()[i]);
	}
	
	vehicles2 = vehicles1;
	n = 0;
	
	for (it1 = vehicles1.begin() ; it1 != vehicles1.end() ; ++it1)
	{
		// ajouter mouvement intra sur it1
		//inBuffer[n++] = moMoves[INTRA][SWAP][*it1];
		
		if (n >= inMax)
			break;
		
		for (it2 = vehicles2.begin() ; it2 != vehicles2.end() ; ++it2)
		{
			if (*it1 == *it2)
				continue;
			
			inBuffer[n++] = moMoves[INTER][OR_OPT][(*it1) * moVRPTW.size() + (*it2)];			
			inBuffer[n++] = moMoves[INTER][OR_OPT][(*it2) * moVRPTW.size() + (*it1)];
			
			if (n >= inMax)
				break;
		}
		
		if (n >= inMax)
			break;
	}
	
	for (it1 = vehicles1.begin() ; it1 != vehicles1.end() ; ++it1)
	{
		// ajouter mouvement intra sur it1
		//inBuffer[n++] = moMoves[INTRA][SWAP][*it1];
		
		if (n >= inMax)
			break;
		
		for (it2 = vehicles2.begin() ; it2 != vehicles2.end() ; ++it2)
		{
			if (*it1 == *it2)
				continue;
			
			//inBuffer[n++] = moMoves[INTER][OR_OPT][(*it1) * moVRPTW.size() + (*it2)];			
			//inBuffer[n++] = moMoves[INTER][OR_OPT][(*it2) * moVRPTW.size() + (*it1)];
			//inBuffer[n++] = moMoves[INTER][TWO_OPT_S][(*it2) * moVRPTW.size() + (*it1)];
			inBuffer[n++] = moMoves[INTER][TWO_OPT_S][(*it1) * moVRPTW.size() + (*it2)];
			
			if (n >= inMax)
				break;
		}
		
		if (n >= inMax)
			break;
	}
	
	return (n);
}




